\contentsline {section}{\numberline {1}Chap1 introduction}{3}{section.1}
\contentsline {section}{\numberline {2}chap2 scanning}{3}{section.2}
\contentsline {section}{\numberline {3}Chap3 context-free grammars and parsing}{4}{section.3}
\contentsline {subsection}{\numberline {3.1}context-free grammars}{4}{subsection.3.1}
\contentsline {subsection}{\numberline {3.2}Parse tree and abstract syntax trees}{4}{subsection.3.2}
\contentsline {subsubsection}{\numberline {3.2.1}parse tree}{4}{subsubsection.3.2.1}
\contentsline {subsubsection}{\numberline {3.2.2}abstract symtax tree}{4}{subsubsection.3.2.2}
\contentsline {subsection}{\numberline {3.3}Ambiguity}{4}{subsection.3.3}
\contentsline {subsubsection}{\numberline {3.3.1}ambiguity grammars}{4}{subsubsection.3.3.1}
\contentsline {subsubsection}{\numberline {3.3.2}precedence and associativity}{5}{subsubsection.3.3.2}
\contentsline {subsubsection}{\numberline {3.3.3}the dangling else problem}{5}{subsubsection.3.3.3}
\contentsline {subsubsection}{\numberline {3.3.4}inessential ambiguity}{5}{subsubsection.3.3.4}
\contentsline {subsubsection}{\numberline {3.3.5}extended notations: EBNF and syntax diagrams}{5}{subsubsection.3.3.5}
\contentsline {subsection}{\numberline {3.4}Formal properties of context-free language}{6}{subsection.3.4}
\contentsline {section}{\numberline {4}Chap4 top-down parsing}{6}{section.4}
\contentsline {subsection}{\numberline {4.1}Top-down parsing by recursive-descent}{6}{subsection.4.1}
\contentsline {subsection}{\numberline {4.2}LL(1) parsing}{6}{subsection.4.2}
\contentsline {subsubsection}{\numberline {4.2.1}LL(1) parsing table}{7}{subsubsection.4.2.1}
\contentsline {subsubsection}{\numberline {4.2.2}left recursion removal and left factoring}{7}{subsubsection.4.2.2}
\contentsline {subsubsection}{\numberline {4.2.3}Syntax tree construction in LL(1) parsing}{8}{subsubsection.4.2.3}
\contentsline {subsection}{\numberline {4.3}First and follow sets}{8}{subsection.4.3}
\contentsline {subsection}{\numberline {4.4}Error recovery in top-down parsers}{8}{subsection.4.4}
\contentsline {section}{\numberline {5}Chap5 Bottom-up parsing}{8}{section.5}
\contentsline {subsection}{\numberline {5.1}Overview of bottom-up parsing}{8}{subsection.5.1}
\contentsline {subsection}{\numberline {5.2}Finite automata of LR(0) items and LR(0) parsing}{11}{subsection.5.2}
\contentsline {subsubsection}{\numberline {5.2.1}Finite automata of items}{11}{subsubsection.5.2.1}
\contentsline {subsubsection}{\numberline {5.2.2}The LR(0) parsing algorithm}{12}{subsubsection.5.2.2}
\contentsline {subsection}{\numberline {5.3}SLR(1) Parsing (simple LR(1))}{13}{subsection.5.3}
\contentsline {subsubsection}{\numberline {5.3.1}disambiguating rules for parsing conflicts}{14}{subsubsection.5.3.1}
\contentsline {subsubsection}{\numberline {5.3.2}limits of SLR(1) parsing power}{14}{subsubsection.5.3.2}
\contentsline {subsection}{\numberline {5.4}General LR(1) and LALR(1) parsing}{14}{subsection.5.4}
\contentsline {subsubsection}{\numberline {5.4.1}Finite automata of LR(1) items}{14}{subsubsection.5.4.1}
\contentsline {subsubsection}{\numberline {5.4.2}The LR(1) parsing algorithm}{15}{subsubsection.5.4.2}
\contentsline {subsection}{\numberline {5.5}LALR(1) parsing}{15}{subsection.5.5}
\contentsline {subsection}{\numberline {5.6}Error recovery in Bottom-up parsers}{15}{subsection.5.6}
\contentsline {section}{\numberline {6}chap6 semantics analysis}{16}{section.6}
\contentsline {subsection}{\numberline {6.1}Attributes and attribute grammars}{16}{subsection.6.1}
\contentsline {subsubsection}{\numberline {6.1.1}attribute grammars}{16}{subsubsection.6.1.1}
\contentsline {subsubsection}{\numberline {6.1.2}simplifications and extensions to attribute grammars}{17}{subsubsection.6.1.2}
\contentsline {subsection}{\numberline {6.2}Algorithms for attribute computation}{17}{subsection.6.2}
\contentsline {subsubsection}{\numberline {6.2.1}dependency graphs and evaluation order}{17}{subsubsection.6.2.1}
\contentsline {subsubsection}{\numberline {6.2.2}synthesized and inherited attributes}{19}{subsubsection.6.2.2}
\contentsline {subsubsection}{\numberline {6.2.3}attributes as parameters and returned values}{19}{subsubsection.6.2.3}
\contentsline {subsubsection}{\numberline {6.2.4}The use of external data structures to store attributes values}{19}{subsubsection.6.2.4}
\contentsline {subsubsection}{\numberline {6.2.5}The computation of attributes during parsing}{20}{subsubsection.6.2.5}
\contentsline {subsubsection}{\numberline {6.2.6}The dependence of attributes computation on the syntax}{21}{subsubsection.6.2.6}
\contentsline {subsection}{\numberline {6.3}The Symbol Table}{21}{subsection.6.3}
\contentsline {subsubsection}{\numberline {6.3.1}The structure of the symbol table}{21}{subsubsection.6.3.1}
\contentsline {subsubsection}{\numberline {6.3.2}Declarations}{21}{subsubsection.6.3.2}
\contentsline {subsubsection}{\numberline {6.3.3}Scope rules and block structure}{22}{subsubsection.6.3.3}
\contentsline {subsubsection}{\numberline {6.3.4}interaction of same-level declarations}{22}{subsubsection.6.3.4}
\contentsline {subsubsection}{\numberline {6.3.5}an extended example of an attribute grammar using a symbol table}{22}{subsubsection.6.3.5}
\contentsline {subsection}{\numberline {6.4}Data types and type checking}{24}{subsection.6.4}
\contentsline {subsubsection}{\numberline {6.4.1}type names, type declarations and recursive type}{24}{subsubsection.6.4.1}
\contentsline {subsubsection}{\numberline {6.4.2}type equivalence}{24}{subsubsection.6.4.2}
\contentsline {subsubsection}{\numberline {6.4.3}type inference and type checking}{24}{subsubsection.6.4.3}
\contentsline {subsubsection}{\numberline {6.4.4}additional topics in type checking}{24}{subsubsection.6.4.4}
\contentsline {section}{\numberline {7}Chap7 runtime environments}{24}{section.7}
\contentsline {subsection}{\numberline {7.1}memory organization during program execution}{24}{subsection.7.1}
\contentsline {subsection}{\numberline {7.2}fully static runtime environment}{25}{subsection.7.2}
\contentsline {subsection}{\numberline {7.3}stack-based runtime environments}{26}{subsection.7.3}
\contentsline {subsubsection}{\numberline {7.3.1}stack-based environments without local procedures}{26}{subsubsection.7.3.1}
